﻿// ParseExpression.cpp : C++表达式求值（利用二叉树和栈分别描述）_基于二叉树的表达式求值算法 
//求例如“（123 - 5） * 6 + （9 - 8） * （5 - 6） - （10 - 2 * （3 - 9））”这样的表达式的值。
/*
此类问题有两种方法可以解答，第一种是利用二叉树的性质，构建表达树栈。第二种方法是利用两个栈，一个放运算符，一个放数据，通过优先级顺序进行运算操作。

1）利用二叉树描述

首先建立表达式树栈，把整个表达式按照优先级分解成各个子表达式，把子表达式分配给二叉树的节点构成表达树栈。表达树栈建好之后就可以从根节点开始递归计算表达式的值。表达树栈的建立过程如下：

*/

#include <iostream>
#include <string>
#include <stack>

using namespace std;

struct expression
{
    char op;

    expression* left;

    expression* right;

    double value;

    expression(char theOp) :op(theOp), left(nullptr), right(nullptr) {  }

    expression(double theValue) :value(theValue), op('#') {
        left = right = nullptr;
    }
};

class expTree
{
public:

    expTree() :root(nullptr) {}
    expTree(const string& str)
    {
        int n = str.size() - 1;

        GenExpTree(str.c_str(), 0, n, root);
    }

    ~expTree() { postOrderErase(root); }

    void postOrderErase(expression*& exp)
    {

        if (exp != nullptr) {

            postOrderErase(exp->left);

            postOrderErase(exp->right);

            delete exp;
        }
    }

    double calculate() { return myCal(root); }

    double myCal(expression*& exp)
    {
        if (exp != nullptr) {

            if (exp->op == '#') {

                return exp->value;

            }

            double x = myCal(exp->left);

            double y = myCal(exp->right);

            switch (exp->op)

            {

            case'+':return x + y;

            case'-':return x - y;

            case'*':return x * y;

            case'/':return x / y;

            }
        }
    }
    void GenExpTree(const char* str, int b, int e, expression*& exp);
private:

    expression* root;
};

void expTree::GenExpTree(const char * str, int b, int e, expression*& exp)
{
    if (b < e && str[b] == '(') {//找到和第一个括号相匹配的')'

        int i = 0, j = b;

        for (; j <= e; j++) {

            if (str[j] == '(') {

                ++i;

            }

            else if (str[j] == ')') {

                --i;

            }

            if (i == 0) {

                break;

            }

        }

        if (j == e) {

            ++b, --e;

        }

    }

    if (b > e) {

        exp = nullptr;

        return;

    }

    int brackets = 0;

    int lastPS = -1, lastMD = -1;

    bool findChar = false;

    for (int i = b; i <= e; i++)
    {
        if (str[i] != '.' && str[i] < '0' || str[i]>'9') {

            findChar = true;

            switch (str[i])

            {

            case'(': brackets++; break;

            case')': brackets--; break;

            case'+':

            case'-': if (!brackets)lastPS = i; break;

            case'*':

            case'/': if (!brackets)lastMD = i; break;

            }
        }
    }

    if (!findChar) {
        char ec = str[e];
        exp = new expression(stod(str + b));
        *(char *)(str + e) = ec;

        return;
    }

    if (lastPS == -1) {
        lastPS = lastMD;
    }

    exp = new expression(str[lastPS]);

    GenExpTree(str, b, lastPS - 1, exp->left);

    GenExpTree(str, lastPS + 1, e, exp->right);
}



void testExpTree()
{
    string str = "(123-5)*6+(9-8)*(5-6)-(10-2*(3+8))+8*(9-1)";

    expTree expT(str);

    cout << expT.calculate() << endl;   //输出783
}
/*
2）利用两个栈来描述

一个栈用来放运算符，另一个栈用来放数据。基本的思想是，如果运算符栈为空，则直接把运算符添加到运算符栈，否则，要比较栈外和栈内的运算符优先级，如果栈内的运算符优先级高（包括栈内的运算符和栈外的运算符处于一个优先级，也认为是栈内的优先级高）则把栈内运算符弹出，再把弹出两个数据符进行运算，把结果再次压入数据符栈, 当然新来的运算符也要入运算符栈。如果栈外的运算符高，则直接把运算符压入运算符栈。如果遇见了‘)’，则说明有一对括号了，此时要把括号里的值计算好，把结果压入数据栈，当然‘)’不入栈，而且要把之前的‘(’删除。最后如果遍历过程中遇见的是数据符，则直接查找长度，把持续的数据先进行数据转换stod, 再把结果压入数据栈。遍历完成后，也许因为优先级的关系，有些数据还没计算，此时的运算优先级是完全按照栈的出栈顺序来的，因此直接出栈计算，直到运算符栈为空，此时的数据栈也只剩一个元素就是最后的计算结果，返回此唯一的栈顶元素。
*/

int priority(char a, char b)
{

    if (b == '+' || b == '-')
    {
        if (a == '+' || a == '-' || a == '*' || a == '/') {

            return 1;
        }

        else if (a == '(') {
            return -1;
        }
    }

    else if (b == '*' || b == '/') {
        if (a == '*' || a == '/') {

            return 1;
        }
        else if (a == '+' || a == '-' || a == '(') {
            return -1;
        }
    }

    else if (b == '(') {
        return -1;
    }

    return 0;
}

template<typename t>
t calculate_t(t x, char op, t y) {
    switch (op)
    {

    case '+':return x + y;

    case '-':return x - y;

    case '*':return x * y;

    case '/':return x / y;
    default:
        return 0;
    }
}

uint16_t calculate(uint16_t x, char op, uint16_t y) {
    switch (op) {
    case '&':return x & y;
    case '>':return x >> y;
    case '<':return x << y;
    default:
        return calculate_t<uint16_t>(x, op, y);
    }
}

double calculate(double x, char op, double y)
{
    return calculate_t<double>(x, op, y);
}

double expStack(const string& str)
{
    stack<char> opor;

    stack<double>opnd;

    int i = 0;

    while (i < str.size()) {

        if (str[i] != '.' && str[i] < '0' || str[i]>'9') {

            if (opor.empty() || priority(opor.top(), str[i]) < 0) {

                opor.push(str[i]);

            }

            else if (priority(opor.top(), str[i]) > 0) {

                double a = opnd.top();

                opnd.pop();

                double b = opnd.top();

                opnd.pop();

                opnd.push(calculate(b, opor.top(), a));

                opor.pop();

                opor.push(str[i]);

            }

            else if (str[i] == ')') {
                while (opor.top() != '(') {

                    double a = opnd.top();

                    opnd.pop();

                    double b = opnd.top();

                    opnd.pop();

                    opnd.push(calculate(b, opor.top(), a));

                    opor.pop();
                }

                opor.pop();
            }

            ++i;
        }

        else {

            int k = i;

            while (str[i] == '.' || str[i] >= '0' && str[i] <= '9') {
                i++;
            }

            opnd.push(stod(str.substr(k, i - k)));
        }
    }

    while (!opor.empty()) {

        double a = opnd.top();

        opnd.pop();

        double b = opnd.top();

        opnd.pop();

        opnd.push(calculate(b, opor.top(), a));

        opor.pop();
    }

    return opnd.top();
}

void testExpStack()
{
    string str = "(123-5)*6+(9-8)*(5-6)-(10-2*(3+8))+8*(9-1)";

    cout << expStack(str) << endl;
}
//优先级
// 1.[] ,()
// 2.- ~ ++ -- ! (类型转换) sizeof
// 3. / * % 
// 4. + -
// 5. << >>
// 6. > >= < <=
// 7. == !=
// 8. &
// 9. ^
// 10. |
// 11. &&
// 12. ||
// 13. ?:

int main()
{
    testExpTree();
    testExpStack();

    uint16_t v = 0x0320;
    const char* value = "((($0&0xf000)>>12)&0x000f)*1000 + ((($0&0x0f00)>>8)&0x000f)*100+ ($0&0x00f0)>>4 + $0&0x08*0.5 + $0&0x7*10000";
    expTree expT(value);
}


